package com.demo40_组合总合2;

import java.util.*;
import java.util.stream.Collectors;

public class Solution2 {
    public static void main(String[] args) {
        int[] ints=new int[]{14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12};
        List<List<Integer>> lists =combinationSum2(ints, 27);

        System.out.println(lists);
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> arrayList=new ArrayList<>();
        ArrayList<Integer> path= new ArrayList<>();
        int sum=0;

        Arrays.sort(candidates);
        dfs(arrayList,path,candidates,0,target,sum);

        //定义 treeset 去重
        TreeSet<List<Integer>> set = new TreeSet<List<Integer>>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                int diff = o1.size() - o2.size();
                //集合长度相同
                if (diff==0){
                    for (int i = 0; i < o1.size(); i++) {
                        if (o1.get(i)!=(o2.get(i))){
                            return 1;
                        }
                    }
                    return 0;
                }else {
                    //集合长度不同
                    return 1;
                }
            }
        });

        for (List<Integer> integers : arrayList) {
            set.add(integers);
        }
        List<List<Integer>> resultList=new ArrayList<>();
        for (List<Integer> item : set) {
            resultList.add(item);
        }



        return resultList;
    }

    private static void dfs(List<List<Integer>> arrayList, ArrayList<Integer> path, int[] candidates, int startIndex, int target, int sum) {
        //1.边界条件
        if (sum==target){
            ArrayList<Integer> copy = new ArrayList<>();
            for (Integer integer : path) {
                copy.add(integer);
            }
            arrayList.add(copy);
            return;
        }

        //2.横向遍历
        for (int i = startIndex; (i < candidates.length)&&(sum+candidates[i]<=target); i++) {
            //处理本次遍历
            sum+=candidates[i];
            path.add(candidates[i]);
            //3.纵向递归
            dfs(arrayList,path,candidates,i+1,target,sum);
            //4.【回溯】
            sum-=candidates[i];
            path.remove(path.size()-1);
        }

    }
}
